package priority_queue;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于动态数组实现的最大堆
 */
public class MaxHeap {
    //实际存储元素的数组
    private List<Integer> elementData;
    //当前堆中的元素个数
    private int size;

    public MaxHeap(){
        this(10);
    }

    public MaxHeap(int size) {
        elementData = new ArrayList<>();
    }

    /**
     * 找到当前节点的父节点的索引
     * @param k
     * @return
     */
    public int parentnode(int k){
        return (k-1)/2;
    }

    /**
     * 找到当前节点的左子树节点索引
     * @param k
     * @return
     */
    public int leftchikd(int k){
         return (2*k)+1;
    }

    /**
     * 找到当前节点的右子树节点索引
     * @param k
     * @return
     */
    public int rightchild(int k){
        return (2*k)+2;
    }

    /**
     * 查看堆中的最大元素
     * @return
     */
    public int peekMax(){
        if (isEmpty()){
            throw new NoSuchElementException("heap is empty!cannot peek!");
        }
        return elementData.get(0);
    }

    /***
     * 判断当前堆是否为空
     * @return
     */
    public boolean isEmpty(){
        return size==0;
    }

    public int getSize(){
        return size;
    }

    /**
     * 在堆中添加元素操作
     * @param val
     */
    public void add( int  val){
        //先在数组尾部添加元素
        elementData.add(val);
        size++;
        //进行元素的上浮操作
        siftUP(size-1);
    }
    /**
     * 元素上浮操作
     * @param k
     */
    private void siftUP(int k) {
        while (k>0&&elementData.get(k)>elementData.get(parentnode(k))){
            swap(k,parentnode(k));
            k=parentnode(k);
        }
    }
    /**
     * 交换元素值操作
     * @param k
     * @param parentnode
     */
    private void swap(int k, int parentnode) {
        int childval=elementData.get(k);
        int parentval=elementData.get(parentnode(k));
        elementData.set(k,parentval);
        elementData.set(parentnode,childval);
    }

    @Override
    public String toString() {
        return elementData.toString();
    }

    /**
     * 取出当前堆的最大值
     * @return
     */
    public int extractMax(){
        if (size==0){
            throw new NoSuchElementException("heap is empty!cannot extractMax!!");
        }
        //最大堆的根节点就是最大值
        int max=elementData.get(0);
        //将数组的末尾元素顶到堆顶
        elementData.set(0,elementData.get(size-1));
        //删除堆的最后一个元素
        elementData.remove(size-1);
        size--;
        //进行元素的下沉操作，从当前根节点开始
        siftDown(0);
        return max;
    }

    /**
     * 从索引k开始进行元素的下沉操作
     * @param k
     */
    private void siftDown(int k) {
        while (leftchikd(k)<size){
            //说明当前节点此时还存在子树
            int j=leftchikd(k);
            if (j+1<size&&elementData.get(j+1)>elementData.get(j)){
                //此时还存在右子树并且右子树的值比左子树的大
                j++;
            }
            //此时索引j就是当前节点中左右子树的最大节点值的索引
            if (elementData.get(k)>=elementData.get(j)) {
                //此时说明当前元素小于左右子树的最大值，就进行交换操作
                break;
            }else {
                swap(j,k);
                k=j;
            }
        }
    }

    /**
     * 将任意数组arr转换为最大堆
     * @param arr
     */
    public MaxHeap(int[] arr){
          elementData= new ArrayList<>(arr.length);
        //先将所有元素都复制到elementData中
        for (int i:arr) {
            elementData.add(i);
            size++;
        }
        //从最后一个非叶子节点开始不断向前进行siftDown操作
        //最后一个非叶子节点就是最后一个节点的父节点，及（size-1）/2
        for (int i = parentnode(size-1); i >=0; i--) {
            siftDown(i);
        }
    }
}
